import random


class InsertionSort:
    """
    插入排序类，包含直接插入排序和希尔排序算法的实现。
    """

    @staticmethod
    def insertion_sort(arr):
        """
        直接插入排序算法的核心思想是将待排序的元素逐个插入到已排序序列的合适位置。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：直接插入排序中，只有当插入元素小于等于已排序元素时才进行插入，相同元素的相对顺序不会改变。
        """
        n = len(arr)

        # 步骤 1: 从第二个元素开始插入到已排序序列的合适位置
        for i in range(1, n):
            key = arr[i]
            j = i - 1

            # 步骤 2: 将比插入元素大的元素向右移动
            while j >= 0 and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1

            # 步骤 3: 将插入元素放到正确的位置
            arr[j + 1] = key

        return arr

    @staticmethod
    def shell_sort(arr):
        """
        希尔排序算法的核心思想是将待排序的列表按照一定增量分组，对每个分组进行插入排序，逐步减小增量直至为1。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        不是稳定排序算法。
        原因：希尔排序中，元素的交换和移动是基于增量间隔的，相同元素可能会交换位置，导致相对顺序改变。
        """
        n = len(arr)
        gap = n // 2

        # 步骤 1: 根据增量分组，对每个分组进行插入排序
        while gap > 0:
            for i in range(gap, n):
                temp = arr[i]
                j = i

                # 步骤 2: 对分组内的元素进行插入排序
                while j >= gap and arr[j - gap] > temp:
                    arr[j] = arr[j - gap]
                    j -= gap

                # 步骤 3: 将插入元素放到正确的位置
                arr[j] = temp

            # 步骤 4: 减小增量
            gap //= 2

        return arr


# 主程序
if __name__ == "__main__":
    # 生成随机输入列表
    input_list = random.sample(range(1, 101), 10)
    print("随机输入列表:", input_list)

    # 创建 InsertionSort 对象
    sorter = InsertionSort()

    # 调用直接插入排序方法进行排序
    sorted_list_insertion = sorter.insertion_sort(input_list)
    # 输出结果
    print("直接插入排序后的列表:", sorted_list_insertion)  # 直接插入排序后的列表: [1, 2, 4, 5, 7]

    # 调用希尔排序方法进行排序
    sorted_list_shell = sorter.shell_sort(input_list)
    # 输出结果
    print("希尔排序后的列表:", sorted_list_shell)  # 希尔排序后的列表: [1, 2, 4, 5, 7]
